\subsection[K-Nearest Neighbors]{Classification par K-Nearest Neighbors}

\noindent La méthode des K-Nearest Neighbors (Knn) est un algorithme très simple permettant de classifier en se basant sur le voisinage d'un échantillon. Généralement un voisinage euclidien est choisi. L'algorithme Knn est sensible à la structure locale des données et donc au bruit. La figure \ref{knn} montre un exemple de décision que pourrait produire Knn. Le point vert peut être classifier comme étant un bleu ou un rouge. Si $k=3$ alors il sera classifier comme étant un rouge (2 rouges pour 1 bleu) alors que si on prend $k=5$ il sera un bleu (3 bleus pour 2 rouges). L'avantage du Knn est que l'on peut rajouter des données d'apprentissage sans qu'il y ai besoin de tout recalculer.

\vspace{0.5cm}
\begin{figure}[h]
\centering
\includegraphics[scale=0.6]{images/knn.png}
\caption{Exemple de Knn(\url{http://en.wikipedia.org/wiki/File:KnnClassification.svg})}
\label{knn}
\end{figure}

\noindent La figure suivante présente une séparation par Knn entre les classes rgb1 et rgb3. L'erreur de classification est de l'ordre de 11\%.

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{images/knn1.png}
\caption{Séparation par knn des classe rgb2 et rgb3}
\end{figure}

On peut voir la droite de séparation passe bien entre les deux classe d'apprentissages (rouge et bleue). Cependant, la classe test étant associée à rgb2 est située entre la classe rgb1 et la classe rgb2. Une petite partie de cette classe test est donc assimilé à la mauvaise classe.\\

\newpage
\subsubsection*{influence du nombre de plus proches voisins}
\begin{figure}[h!]
\centering
\includegraphics[scale=0.45]{images/knn_success_size.png}
\caption{Influence de la taille du voisinage sur le taux de bonne classification (gauche) et sur le temps d'exécution (droite) entre rgb2 et rgb3 et la classe de test rgb2\_t}
\label{knn_success_size}
\end{figure}

\newpage
\noindent La figure \ref{knn_success_size} représente sur la partie gauche l'influence de la taille du voisinage lors de l'exécution de \texttt{knn} sur le taux de réussite de classification entre les classes rgb2 et rgb3 et la classe de test rgb2\_t. Sur la partie de droite, est représenté le temps d'exécution de l'algorithme en fonction de la taille du voisinage. Le test à été fait avec la totalité des échantillons de chacune des classes.\\
Nous pouvons voir que plus la taille du voisinage est importante, et meilleur est le taux de bonne classification. Cependant, le gain est surtout visible lorsque l'on passe de 1 voisin à 17 voisins. Au delà, le taux de bonne réponse n'évolue que très peu.\\
Pour ce qui est du temps d'exécution, plus le nombre de voisins est important, et plus l'algorithme met de temps pour terminer. Il s'agit ici d'une complexité linéaire.\\



\begin{figure}[h!]
\centering
\begin{tabular}{|l||c|c|c|c|}
   \hline
   Échantillon test& \texttt{RGB1} & \texttt{RGB2} & \texttt{RGB3} & \texttt{RGB4} \\
   \hline\hline
   \texttt{RGB1\_V} & 33 & \textcolor{red}{63} &  & \\
   \texttt{RGB2\_V} & 0 & \textcolor{green}{1} &  & \\
   \hline
   \texttt{RGB1\_V} & 0.01 & & \textcolor{red}{99} & \\
   \texttt{RGB3\_V} & 0.05 & & \textcolor{green}{0.95} & \\
   \hline   
   \texttt{RGB1\_V} & \textcolor{green}{0.53} & & & 0.47 \\
   \texttt{RGB4\_V} & 0 & & & \textcolor{green}{1} \\
   \hline
   \texttt{RGB2\_V} & & \textcolor{green}{0.96} & 0.04 & \\
   \texttt{RGB3\_V} & & 0.02 & \textcolor{green}{0.98} & \\
   \hline
   \texttt{RGB2\_V} & & 0.36 & & \textcolor{red}{0.64}\\
   \texttt{RGB4\_V} & & 0.40 & & \textcolor{green}{0.60} \\
   \hline
   \texttt{RGB3\_V} & & & \textcolor{green}{0.98} & 0.02 \\
   \texttt{RGB4\_V} & & & 0 & \textcolor{green}{1} \\
   \hline
\end{tabular}
\caption{Test d'un échantillon avec deux classes \texttt{RGB} en utilisant \texttt{Knn}}
\label{tab_knn}
\end{figure}

\noindent Le tableau ci-dessus (cf figure \ref{tab_knn}) explicite la classification avec Knn. Les colonnes représentent l'ensemble de classe d'apprentissage, et le ligne, l'ensemble des classe de test. En rouge est donnée le taux de bonne classification d'une classe test avec deux classe d'apprentissage, et en rouge, le taux de mauvaises classification.\\
On peut voir que la classe test 1 est très mal classifiée, que ce soit en confrontant rgb1 à rgb2, rgb3, et même rgb4. On peut l'expliquer par le fait que la classe test rgb1\_t est très mal placé, et ne correspond à aucune classe d'apprentissage (cf figure \ref{rgb1t_vs_all}). On remarque également qu'en faisant confronter les classe rgb2 et rgb4, les résultats ne sont pas satisfaisant, que ce soit rgb2\_t ou rgb4\_t comme classe de test. Comme dit plus tot, c'est dû au fait que ces deux classes d'apprentissage sont mélangée l'une l'autre.\\
L'ensemble des autres classes sont correctement classifiées.\\

\newpage

\begin{figure}[h!]
\centering
\includegraphics[scale=0.4]{images/allrgb1t.png}
\caption{Confrontation entre rgb1\_t et les quatres classes test}
\label{rgb1t_vs_all}
\end{figure}

\noindent On remarque sur la figure \ref{rgb1t_vs_all} que la classe test rgb1\_t est très mal positionnée, et ne semble correspondre à aucune classe d'apprentissage.\\
